#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

struct Compare {
    bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.second > b.second; 
    }
};

std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
    std::unordered_map<int, int> freqMap;
    for (int num : nums) {
        freqMap[num]++;
    }

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Compare> minHeap;
    for (auto it = freqMap.begin(); it != freqMap.end(); ++it) {
        if (minHeap.size() < k) {
            minHeap.push({it->first, it->second});
        } else {
            if (it->second > minHeap.top().second) {
                minHeap.pop();
                minHeap.push({it->first, it->second});
            }
        }
    }

    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }

    return result;
}

int main() {
    std::vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;
    std::vector<int> result = topKFrequent(nums, k);

    std::cout << "Top " << k << " frequent elements are: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}